package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no85;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();

    }

    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    int size = getMaxMatrix(i, j, matrix);
                    if (size > max) {
                        max = size;
                    }
                }
            }
        }
        return max;
    }

    private int getMaxMatrix(int i, int j, char[][] matrix) {
        int max = 1;
        int maxy = matrix[i].length;
        for (int x = i; x < matrix.length; x++) {
            if (matrix[x][j] == '0') {
                break;
            }
            int y = j;
            for (; y < maxy; ) {
                if (matrix[x][y] == '0') {
                    if(maxy > y){
                        maxy = y;
                    }
                    break;
                }
                else{
                    y++;
                }
            }
            int size = (x - i + 1) * (y - j);
            if (size > max) {
                max = size;
            }
        }
        return max;
    }

}
